1. Field of the Invention
The present invention relates to an architecture for a field programmable gate array (FPGA). More specifically, the present invention relates to an FPGA that includes a plurality of configurable logic blocks (CLBs), each having a configurable logic element (CLE) and an associated multiplier tile.
2. Related Art
FIG. 1A is a representation of the binary multiplication of a 4-bit multiplicand number X with a 4-bit multiplier word Y. Multiplicand number X includes bits X3, X2, X1 and XO (X3 being the most significant bit and X0 being the least significant bit). Similarly, multiplier word Y includes bits Y3, Y2, Y1 and Y0 (Y3 being the most significant bit and Y0 being the least significant bit). Each bit of multiplicand number X is multiplied by each bit of multiplier word Y as illustrated, thereby creating four partial products 101-104. The first partial product 101 includes each bit of multiplicand number X multiplied by Y0. The second partial product 102 includes each bit of multiplier number X multiplied by Y1. The second partial product 102 is shifted left one place with respect to the first partial product 101, thereby providing the appropriate weight to these partial products. The third and fourth partial products 103 and 104 are created and weighted in a similar manner. The aligned columns of partial products 101-104 are added to create product bits P7-P0. Product bits P7-P0 represent the product P of multiplicand number X and multiplier word Y.
FIG. 1B illustrates the addition of partial products 101-104 in more detail. As illustrated in FIG. 1B, the first and second partial products 101 and 102 are initially added. The values in each column are added, thereby generating six sum signals (C4, PP2, PP1, PP0, P1 and P0) and four carry signals (C1-C4) as illustrated. The sum and carry signals for each column are generated in response to the three input signals associated with the column. The generation of sum and carry signals in response to three generic input signals A, B and C is summarized below in Table 1.
TABLE 1 ______________________________________ A B C SUM CARRY ______________________________________ 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 ______________________________________
Carry signal C1 is the carry result from the addition of X1Y0, X0Y1 and "0". Similarly, carry signal C2 is the carry result from the addition of X2Y0, X1Y1 and C1. Carry signal C3 is the carry result from the addition of X3Y0, X2Y1 and C2. Finally, carry signal C4 is the carry result from the addition of X3Y1, C3 and "0".
Six sum signals (C4, PP2, PP1, PP0, P1 and P0) result from the addition of partial products 101 and 102. Sum signal P0 (which is also product bit P0) is equal to X0Y0. Sum signal P1 (which is also product bit P1) is the sum result of XLY0, X0Yi and "0". Sum signal PP0 is the sum result of X2Y0, X1Y1 and C1. Sum signal PP1 is the sum result of X3Y0, X2Y1 and C2. Sum signal PP2 is the sum result of X3Y1 and C3.
Partial product 103 is added to the six sum signals that result from the addition of partial products 101 and 102. Seven sum signals (C8, PP5, PP4, PP3, P2, P1 and P0) and four carry signals (C5-C8) are generated by this addition operation as illustrated. Partial product 104 is then added to the seven sum signals resulting from the addition of partial products 101, 102 and 103. Sum signals (i.e., the product bits P7-P0) and carry signals C9-C12 are generated during this addition operation as illustrated.
FIG. 2 is a circuit diagram of a conventional 4.times.4 bit multiplier circuit 200 for implementing the multiplication operation illustrated in FIGS. 1A and 1B. Multiplier circuit 200 includes AND gates 201-216 and adder circuits 221-236. Each of adder circuits 221-236 provides a sum signal and a carry signal in response to three input signals in the manner set forth in Table 1. Each of AND gates 201-216 has a first input terminal which is coupled to receive a selected one of the multiplicand bits X3-X0. Similarly, each of AND gates 201-216 has a second input terminal which is coupled to receive a selected one of the multiplier bits Y3-Y0. AND gates 201-216 operate to multiply the X and Y bits. The truth tables for the logical AND of two bits and the arithmetic product of two bits are identical, the result being a logic "1" value only if both bits have logic "1" values, the result being a logic "0" otherwise. As a result, AND gates 201-216 provide the terms of partial products 101, 102, 103 and 104. More specifically, AND gates 201-204 provide the terms of partial product 101; AND gates 205-208 provide the terms of partial product 102; AND gates 209-212 provide the terms of partial product 103; and AND gates 213-216 provide the terms of partial product 104. The terms of partial products 101-104 are provided to adder circuits 225-236 as illustrated. Note that the terms of partial products 101-104 are shifted down in successive columns, thereby providing the appropriate weighting to the partial products. Adder circuits 221-236 add partial products 101-104 in the manner illustrated in FIG. 1B, thereby creating product bits P7-P0. Adders 221-224 are included for regularity. Since one operand to those adders is zero, they serve only to pass partial product 101 to adders 225-228 where partial product 101 is added to partial product 102. The carry signals C1-C12 and sum signals PP0-PP5 previously described in connection with FIG. 1B are illustrated in FIG. 2, thereby showing the manner in which multiplier circuit 200 implements the multiplication operation of FIG. 1B.
FIG. 3, which includes FIGS. 3A and 3B, is a circuit diagram illustrating the implementation of multiplier circuit 200 in an FPGA. The FPGA includes an array of configurable logic blocks (CLBs), which includes CLBs 301-316. Programmable interconnect resources extend between the CLBs, thereby allowing the illustrated connections to be made. The resources present within each CLB can be configured to implement either a pair of adder circuits or a pair of AND gates. For example, CLB 302 is configured to implement AND gates 201 and 202, and CLB 304 is configured to implement adder circuits 221 and 222. A total of eight CLBs (i.e., CLBs 301-302, 305-306, 309-310 and 313-314) are required to implement AND gates 201-216. A total of eight CLBs (i.e., CLBs 303-304, 307-308, 311-312 and 315-316) are required to implement adder circuits 221-236. As a result, at least sixteen CLBs are required to implement multiplier circuit 200. This typically represents a significant portion of the FPGA resources. As a result, it is fairly inefficient to implement multiplier circuit 200 in an FPGA.
Some FPGAs enable one or more of AND gates 201-202 to be implemented in CLB 304. However, even if both of AND gates 201-202 are implemented in CLB 304, at least eight CLBs are required to implement multiplier circuit 200. Because the number of CLBs required to multiply an N-bit multiplicand by an M-bit multiplier grows in proportion to the product N.times.M, large multipliers can consume a significant portion of the FPGA resources. In general, multiplier circuits cannot be implemented efficiently in a conventional FPGA because of the relatively large number of CLBs required to form the multiplier circuit.
It would therefore be desirable to have an FPGA which is capable of efficiently performing multiplication operations.